Self-propulsion and navigation due to the sensing of environmental conditions—such as durotaxis and chemotaxis—are remarkable properties of biological cells that cannot be modeled by single-component self-propelled particles. Therefore, we introduce and study'flexocytes', deformable vesicles with enclosed attached self-propelled pushing and pulling filaments that align due to steric and membrane-mediated interactions. Using computer simulations in two dimensions, we show that the membrane deforms under the propulsion forces and forms shapes mimicking motile biological cells, such as keratocytes and neutrophils. When interacting with walls or with interfaces between different substrates, the internal structure of a flexocyte reorganizes, resulting in a preferred angle of reflection or deflection, respectively. We predict a correlation between motility patterns, shapes, characteristics of the internal forces, and the response to micropatterned substrates and external stimuli. We propose that engineered flexocytes with desired mechanosensitive capabilities enable the construction of soft-matter microbots.