We show that the dynamics of any open quantum system that is initially correlated with its environment can be described by a set of d(2) (or less) completely positive maps, where d is the dimension of the system. Only one such map is required for the special case of no initial correlations. The same maps describe the dynamics of any system-environment state obtained from the initial state by a local operation on the system. The reduction of the system dynamics to a set of completely positive maps allows known numerical and analytic tools for uncorrelated initial states to be applied to the general case of initially correlated states, which we exemplify by solving the qubit dephasing model for such states, and provides a natural approach to quantum Markovianity for this case. We show that this set of completely positive maps can be experimentally characterized using only local operations on the system, via a generalization of noise spectroscopy protocols. As further applications, we first consider the problem of retrodicting the dynamics of an open quantum system which is in an arbitrary state when it becomes accessible to the experimenter and explore the conditions under which retrodiction is possible. We also introduce a related one-sided or limited-access tomography protocol for determining an arbitrary bipartite state, evolving under a sufficiently rich Hamiltonian, via local operations and measurements on just one component. We simulate this protocol for a physical model of particular relevance to nitrogen-vacancy centers and in particular show how to reconstruct the density matrix of a set of three qubits, interacting via dipolar coupling and in the presence of local magnetic fields, by measuring and controlling only one of them.