We report evidence of a narrow structure, $X(5568)$, in the decay sequence $X(5568) rightarrow B_s^0 pi^{pm}$, $B_s^0 rightarrow J/psi phi$, $J/psirightarrow mu^+ mu^-$, $phi rightarrow K^+K^-$. This is evidence for the first instance of a hadronic state with valence quarks of four different flavors. The mass and natural width of this state are measured to be $m = 5567.8 pm 2.9 {rm thinspace (stat)} ^{+0.9}_{-1.9} {rm thinspace (syst)}$ MeV/$c^2$ and $Gamma = 21.9 pm 6.4 {rm thinspace (stat)} ^{+5.0}_{-2.5} {rm thinspace (syst)} $ MeV/$c^2$. If the decay is $X(5568) rightarrow B_s^* pi^{pm} rightarrow B_s^0 gamma pi^{pm}$ with an unseen $gamma$, $m(X(5568))$ will be shifted up by $m(B_s^*) - m(B_s^0) sim 49$ MeV/$c^2$. This measurement is based on $10.4~rm{fb^{-1}}$ of $p bar p $ collision data at $sqrt{s}$ = 1.96 TeV collected by the D0 experiment at the Fermilab Tevatron collider.