After the input of a subscriber (TLN1) of the first terminal (EG1), a connection to a temporarily available voice memory (SPS) is signalized by the same, and subsequently a voice message (spn) and at least one piece of retrieval information (ai) identifying the second terminal (EG2) is transmitted and stored at that location. Subsequently, the connection is terminated and the second terminal (EG2) is informed of the presence of a retrievable voice message (spn) in the voice memory (SPS) via the voice memory (SPS) by means of the at least one piece of retrieval information (ai), and the voice message (spn) can be retrieved from the second terminal (EG2) by means of the transmitted retrieval information (ai), or is transmitted to the second terminal (EG2) by the voice memory (SPS). In this manner voice messages (spn) can be stored for terminals (EG2) and retrieved by the same, regardless of whether one or no voice memories—such as an answering machine—is associated with these terminals (EG2).