The story
From the Middle English expression al be it (that), itself shortened from althagh it be that (“although it be that”), and thus composed from al (“completely, entirely”, literally “all”) + be (3rd person singular present subjunctive of been (“to be”)) + it.
Etymology from Wiktionary, CC BY-SA 4.0.