We introduce graphene antidot lattice waveguides: nanostructured graphene where a region of pristine graphene is sandwiched between regions of graphene antidot lattices. The band gaps in the surrounding antidot lattices enable localized states to emerge in the central waveguide region. We model the waveguides via a position-dependent mass term in the Dirac approximation of graphene and arrive at analytical results for the dispersion relation and spinor eigenstates of the localized waveguide modes. To include atomistic details we also use a tight-binding model, which is in excellent agreement with the analytical results. The waveguides resemble graphene nanoribbons, but without the particular properties of ribbons that emerge due to the details of the edge. We show that electrons can be guided through kinks without additional resistance and that transport through the waveguides is robust against structural disorder.