This is normally completely straightforward and just a matter of configuring SOAP UI to use BASIC authentication and a user with rights to use the messaging interface (e.g. an admin user).
I assume you mean from the above that you are using the WSDL URL that is generated for you by EDQ (from the Web Services page on the Launchpad).
To put a little meat on this, you need to set an EDQ username and password for a test case in SoapUI in the parameters in the bottom left of the window:
See the Username and Password properties near the bottom left.
The web service tester logs into EDQ the same way as the normal UI and uses the its session to send web service requests. This is something a standalone client would not be able to do.
Assuming your client can support Basic authentication as a minimum, there is nothing special about calling web services in EDQ - just POST your SOAP message at the URL and get the SOAP response back.