Get entry by slug with EntriesService in ElementAPI
Don't know if this is the most efficient way, but you can always get the category using the ElementsService.

$criteria = craft()-&gt;elements-&gt;getCriteria(ElementType::Category);
$criteria-&gt;group = 'categoryGroup';
$criteria-&gt;slug = 'categorySlug';
$categories = $criteria-&gt;find();

$criteria = craft()-&gt;elements-&gt;getCriteria(ElementType::Entry);
$criteria-&gt;section = 'section';
$criteria-&gt;relatedTo = array(
    'targetElement' =&gt; $categories,
    'field'         =&gt; 'relationField'
);
$entries = $criteria-&gt;find();