An effective spin-orbit coupling can be generated in a cold atom system by engineering atom-light interactions. In this Letter we study spin-1/2 and spin-1 Bose-Einstein condensates with Rashba spin-orbit coupling, and find that the condensate wave function will develop nontrivial structures. From numerical simulation we have identified two different phases. In one phase the ground state is a single plane wave, and often we find the system splits into domains and an array of vortices plays the role of a domain wall. In this phase, time-reversal symmetry is broken. In the other phase the condensate wave function is a standing wave, and it forms a spin stripe. The transition between them is driven by interactions between bosons. We also provide an analytical understanding of these results and determine the transition point between the two phases. © 2010 The American Physical Society.