The automorphisms of free groups with boundaries form a family of groups A_{n,k} closely related to mapping class groups, with the standard automorphisms of free groups as A_{n,0} and (essentially) the symmetric automorphisms of free groups as A_{0,k}. We construct a contractible space L_{n,k} on which A_{n,k} acts with finite stabilizers and finite quotient space and deduce a range for the virtual cohomological dimension of A_{n,k}. We also give a presentation of the groups and calculate their first homology group.