Cryptography is a science of converting clear message into secret message "nonreadable message", where message was encrypted at sender side then decrypted at receiver side. Vigenere is an example of substitution cipher, it has various limitations, in this paper we propose an advanced encryption algorithm which improves the security of Vigenere method by combining it with modern cipher method like Stream cipher, Stream cipher relatively regards as unbreakable method, and it uses binary form (instead of characters) where the Plaintext, Ciphertext and the Key are strings of bits. When applying the proposed algorithm, we see that the mentioned above combination cipher has a high degree of security, where cipher based on just Vigenere method is not secure. Also, the proposed algorithm makes the cryptanalysis, using frequency attack, more difficult. General Terms Information security, cryptography