Tissue deformation simulations for pre-operative planning or intra-operative guidance of medical procedures require accurate patient-specific models and are commonly performed using the Finite Element Method (FEM). Since only a small part of the entire body is typically observed with medical imaging, the deformation models are often limited to a relatively small region-of-interest (ROI). Surrounding this ROI, one then needs to define suitable boundary conditions for an accurate simulation. Conventionally, boundary conditions are set arbitrarily or heuristically at chosen model locations; typically as either zero-displacement or -force constraint, which obviously are suboptimal where ROI borders are neither fixed (e.g. on bone) or free (e.g. skin facing the air). In this work, we present a novel boundary-condition formulation, called compliance boundary conditions (CBC), which approximate the effect of anatomy outside this ROI and augment this onto the ROI border nodes. CBC can be parametrized from observed tissue displacements, e.g. tracked in ultrasound (US) or magnetic-resonance imaging (MRI). It is inherently embedded in the FEM deformation model to be used for computing any interaction response. CBC is a generalization of conventional boundary constraints, where the typical zero-displacement and -force constraints are obtained at the two extremes of the given CBC parameter. We demonstrate CBC for linear- and quadratic-strain FEM models in 2D and 3D numerical phantoms, for which different element/integration formulations and the effect of noise are studied. CBC is shown to reduce displacement errors for both 2D and 3D numerical phantoms by more than 50% compared to conventional boundary conditions. We also present CBC on tissue-mimicking gelatin phantom experiments from displacements observed in US images. In an application scenario of simulating needle insertion for prostate brachytherapy, CBC is shown to reduce seed placement errors by more than 70% compared to conventional boundary conditions.