Using density-functional theory calculations, we investigated the electronic structure and magnetic exchange interactions of the ordered 3d-5d double perovskite Sr2FeOsO6, which has recently drawn attention for interesting antiferromagnetic transitions. Our study reveals the vital role played by long-range magnetic exchange interactions in this compound. The competition between the ferromagnetic nearest neighbor Os-O-Fe interaction and antiferromagnetic next nearest neighbor Os-O-Fe-O-Os interaction induces strong frustration in this system, which explains the lattice distortion and magnetic phase transitions observed in experiments.