A method and apparatus for establishing a requested communication session between two terminals (A, B) over a given physical channel, wherein the session requires the determination of session parameters before the session can be executed. It is determined (402) by means of at least one session key, whether any session parameters for a previous session between the terminals have been stored in the terminals. If so, the stored session parameters are retrieved (408), such that the requested session can be executed (410) based on the retrieved session parameters. In this way, delays involved with the establishment of sessions requiring the determination of parameters, e.g. in multimedia calls, can be reduced.