Telewizja Mimo że działalność aktorska Elby rozpoczęła się oficjalnie w 1992, dopiero trzy lata później otrzymał swoją pierwszą rolę w serialu Bramwell. W 1995 roku po raz pierwszy został wymieniony w czołówce, przy okazji występu w jednym z odcinków serialu Absolutnie fantastyczne. W kolejnych latach pojawiał się w rolach drugoplanowych w wielu brytyjskich serialach, w tym m.in.: The Bill, Degrees of Error, The Ruth Rendell Mysteries, The Governor, Family Affairs, Ultraviolet oraz Dangerfield.
Elba podjął decyzję o wyjeździe do Nowego Jorku, a do Anglii wracał tylko po to, aby brać udział w nagraniach, w tym np. serialu Sprawy inspektora Lynleya. W 2001 wystąpił jako Achilles w sztuce Troilus and Cressida. W tym samym roku zagrał w jednym z odcinków serialu Prawo i porządek, a rok później dostał angaż do Prawa ulicy, w którym występował przez dwa lata. W 2005 roku wcielił się w postać kapitana Augustina Muganzy w filmie telewizyjnym Czasem w kwietniu, mówiącym o ludobójstwie w Rwandzie. W 2007 roku Elba pojawił się w specjalnym programie Black Entertainment Television Black Men: The Truth.