We analyze the structural behavior of a single polymer chain grafted to an attractive, flexible surface. Our model is composed of a coarse-grained bead-and-spring polymer and a tethered membrane. By means of extensive parallel tempering Monte Carlo simulations it is shown that the system exhibits a rich phase behavior ranging from highly ordered, compact to extended random coil structures, and from desorbed to completely adsorbed or even partially embedded conformations. These findings are summarized in a pseudophase diagram indicating the predominant class of conformations as a function of the external parameters temperature and polymer-membrane interaction strength. By comparison with adsorption to a stiff membrane surface it is shown that the flexibility of the membrane gives rise to qualitatively new behavior such as stretching of adsorbed conformations.