Space plasma simulations have seen an increase in the use of magnetohydrodynamic (MHD) with embedded Particle-in-Cell (PIC) models. This combined MHD-EPIC algorithm simulates some regions of interest using the kinetic PIC method while employing the MHD description in the rest of the domain. The MHD models are highly efficient and their fluid descriptions are valid for most part of the computational domain, thus making large-scale global simulations feasible. However, in practical applications, the regions where the kinetic effects are critical can be changing, appearing, disappearing and moving in the computational domain. If a static PIC region is used, this requires a much larger PIC domain than actually needed, which can increase the computational cost dramatically. To address the problem, we have developed a new method that is able to dynamically change the region of the computational domain where a PIC model is applied. We have implemented this new MHD with Adaptively Embedded PIC (MHD-AEPIC) algorithm using the BATS-R-US Hall MHD and the Adaptive Mesh Particle Simulator (AMPS) as the semi-implicit PIC models. We describe the algorithm and present a test case of two merging flux ropes to demonstrate its accuracy. The implementation uses dynamic allocation/deallocation of memory and load balancing for efficient parallel execution. We evaluate the performance of MHD-AEPIC compared to MHD-EPIC and the scaling properties of the model to large number of computational cores.