In your REST call are you specifying the X-RequestDigest
parameter in its headers? If not, you need to. Every REST call needs to be authenticated.
You can find an excellent step-by-step guide on how to do this here:
http://blog.appliedis.com/2014/10/09/sharepoint-designer-2013-workflow-working-with-web-services/
In case the link goes dead I copy the text below:
When working with the SharePoint REST services you need to
authenticate the requests.
There is a service available to take care of this. This step will
build a Dictionary object for the request headers and then call the
service to get the security token. First we’ll create a new
Dictionary action, output it to a variable called contextHeaders, and
create entries for Accept, Content-Type, and Content-Length headers.
For Accept and Content-Type, we want to use “application/json;
odata=verbose.” SharePoint 2013 REST calls require the second
parameter, “odata=verbose,” because while the OData specification
supports other options, SharePoint’s services do not.
Next, we’ll create a “Call HTTP Web Service” action to get the token.
Also, you must use the POST method to get this token. While you would
expect to use a GET call, the reason for POST is to improve security
against “shady” requests. Next, we’ll need to assign a variable to
the ResponseContent of the action. This is a Dictionary object we’ll
call contextResponse. Finally, we need to set the RequestHeaders
property of the action to our contextHeaders dictionary.
Right-click on the action and select “Properties…” to access the
action’s properties window.