In this paper, the notion of bi-Boolean independence for non-unital pairs of algebras is introduced thereby extending the notion of Boolean independence to pairs of algebras. The notion of B-$(\ell, r)$-cumulants is defined via a bi-Boolean moment-cumulant formula over the lattice of bi-interval partitions, and it is demonstrated that bi-Boolean independence is equivalent to the vanishing of mixed B-$(\ell, r)$-cumulants. Furthermore, some of the simplest bi-Boolean convolutions are considered, and a bi-Boolean partial $η$-transform is constructed for the study of limit theorems and infinite divisibility with respect to the additive bi-Boolean convolution. In particular, a bi-Boolean Lévy-Hinčin formula is derived in perfect analogy with the bi-free case, and some Bercovici-Pata type bijections are provided. Additional topics considered include the additive bi-Fermi convolution, some relations between the $(\ell, r)$- and B-$(\ell, r)$-cumulants, and bi-Boolean independence in an amalgamated setting. The last section of this paper also includes an errata that will be published with this copy of the paper.