Despite of well-known application of aluminum-based filler metals for brazing titanium, they are still out of everyday industrial practice due to low strength of joints brazed with pure aluminum or standard AWS BAl-4 (Al-12Si) filler metal, and problems in the manufacture of foils or wires from brittle alloys of Al-Cu-Si or Al-Ag-Cu systems. New cold-rolled brazing foils of Al-Mg and Al-Cu-Mg, as well as composite foils of the Al-Ni-Cu-Si and Al-Cu-Ag alloy systems modified with Mg, Fe, and Sn were studied by testing wetting of CP titanium and Ti-6Al-4V substrates in vacuum at the temperature range of 600-710˚C, measuring shear strength of brazed joints, and investigating the microstructure to find out formation of intermetallics in the joints. Some of new brazing alloys demonstrated the joint strength, which is significantly higher than that of traditional Al-12Si eutectic filler metal.