Gelation of α-lactalbumin (α-la) incubated with a protease from Bacillus licheniformis (BLP) at 50 °C for 4 h was monitored using small oscillatory shear and the large deformation properties of final gels were characterized by uniaxial compression. Transmission electron microscopy was used to visualize the microstructure. Gels made from α-la (10 g/l) using BLP were almost transparent, although somewhat whitish, and they were more than 20 times stiffer (measured as complex modulus) than equivalent gels made from β-lactoglobulin (β-lg) at the same concentration. The microstructure of the gels consisted of non-branching, apparently hollow strands with a uniform diameter close to 20 nm, similar in overall structure to microtubules. Adding Ca2+ in amounts of 50 or 100 mM changed the spatial distribution of the strands and resulted in a reduction in the failure stress recorded in uniaxial compression. Apart from affecting the microstructure, Ca2+ was shown to be essential for the formation of the gels. It is proposed, that the mechanism behind the self-assembly of the partially hydrolysed α-la into long tubes is a spatially restricted creation of ionic bonds between Ca2+ and carboxyl acid groups on peptide fragments resulting from the action of BLP on α-la. Proteolysis of α-la with BLP in the presence of Ca2+ thus results in formation of a strong gel with a microstructure not previously observed in food protein systems.