A method for connecting a calling terminal to a called terminal includes establishing a first session to a video server and a call connection request to the called terminal, receiving ringback tone (RBT) video data from the video server using the established first session during a waiting time before a response from the called terminal for the request is received, generating a setup flag to set a connection environment with the called terminal to perform a fast setup between the calling terminal and the called terminal, and transmitting the generated setup flag to the called terminal through a second session established by the called terminal. A system to perform the method includes an establishing unit to establish the first session, an RBT video data receiving unit to receive the RBT video data, a setup flag generating unit, and a setup flag transmitting unit.