Work on formulating general probabilistic theories in an operational context has tended to concentrate on the probabilistic aspects (convex cones and so on) while remaining relatively naive about how the operational structure is built up (combining operations to form composite systems, and so on). In particular, an unsophisticated notion of a background time is usually taken for granted. It pays to be more careful about these matters for two reasons. First, by getting the foundations of the operational structure correct it can be easier to prove theorems. And second, if we want to construct new theories (such as a theory of Quantum Gravity) we need to start out with a sufficiently general operational structure before we introduce probabilities. I will present an operational structure which is sufficient to provide a foundation for the probabilistic concepts necessary to formulate quantum theory. According to Bob Coecke, this operational structure corresponds to a symmetric monoidal category. I will then discuss a more general operational framework (which I call Object Oriented Operationalism) which provides a foundation for a more general probabilistic framework which may be sufficient to formulate a theory of Quantum Gravity. This more general operational structure does not admit an obvious category theoretic formulation.