We study the interaction energy between two graphene nanoribbons by first-principles calculations, including van der Waals interactions and spin polarization. For ultranarrow zigzag nanoribbons, the direct stacking is even more stable than the Bernal stacking, competing in energy for wider ribbons. This behavior is due to the magnetic interaction between edge states. We relate the reduction of the magnetization in zigzag nanoribbons with increasing ribbon width to the structural changes produced by the magnetic interaction, and we show that when deposited on a substrate, zigzag bilayer ribbons remain magnetic for larger widths. © 2012 American Physical Society.