diff --git a/thoth/solver/python.py b/thoth/solver/python.py
index <HASH>..<HASH> 100644
--- a/thoth/solver/python.py
+++ b/thoth/solver/python.py
@@ -136,7 +136,12 @@ def _filter_package_dependencies(package_info: dict) -> dict:
 
 
 def _resolve_versions(package_name: str, version_spec: str) -> typing.List[str]:
-    resolved_versions = _PYPI_SOLVER.solve([package_name + (version_spec or '')], all_versions=True)
+    try:
+        resolved_versions = _PYPI_SOLVER.solve([package_name + (version_spec or '')], all_versions=True)
+    except Exception:  # pylint: disable=broad-except
+        _LOGGER.exception("Failed to resolve versions for %r with version spec %r", package_name, version_spec)
+        return []
+
     assert len(resolved_versions.keys()) == 1,\
         "Resolution of one package version ended with multiple packages."
     return list(resolved_versions.values())[0]
Mark packages that couldn't be found as unresolvable