Sachverhalt:
A.
A.a. A._ (geboren 1969), mazedonischer Staatsangehöriger, reiste 1981 im Alter von zwölf Jahren in die Schweiz ein und verfügte über eine bis zum 8. März 2019 kontrollbefristete Niederlassungsbewilligung. Strafrechtlich ist er in der Schweiz (ohne Straftaten, die im Ordnungsbussenverfahren hätten erledigt werden können) ab 1991 (Tatzeitpunkt) durch zwölf Strafbefehle und zwei Strafurteile in Erscheinung getreten, welche insgesamt zu 61 Monaten Freiheitsstrafe, 135 Tagessätzen Geldstrafe und Fr. 8'250.-- Busse geführt haben. Unter anderem hat das Bezirksgericht Dielsdorf A._ am 10. November 1994 zu zehn Monaten Freiheitsstrafe bedingt wegen mehrfacher Hehlerei, mehrfacher Gehilfenschaft zur Veruntreuung und Fahrens trotz Führerausweisentzug bzw. -verweigerung verurteilt. Die letzte strafrechtliche Sanktionierung erfolgte durch Urteil des Bezirksgerichts Dielsdorf vom 29. November 2016, insbesondere wegen gewerbsmässiger Hehlerei, mehrfacher Veruntreuung, mehrfachem Betrug und betrügerischem Missbrauch einer Datenverarbeitungsanlage, wobei eine Freiheitsstrafe von 45 Monaten ausgesprochen wurde. Das Migrationsamt des Kantons Zürich (Migrationsamt) hat A._ am 8. Juni 2006 und 4. Juni 2012 ausländerrechtlich verwarnt und zuletzt ausdrücklich den Widerruf der Niederlassungsbewilligung im Falle erneuter Straffälligkeit in Aussicht gestellt. Der Betreibungsregisterauszug von A._ des Betreibungsamtes Regensdorf vom 10. September 2013 weist 79 offene Verlustscheine im Gesamtbetrag von fast Fr. 300'000.-- aus, wobei der erste Verlustschein aus dem Jahr 2000 stammt.
A.b. B._ (geboren 1976), armenische Staatsangehörige, reiste im Juni 2013 in die Schweiz ein, ersuchte erfolglos um Asyl und wurde nach ebenfalls erfolglosem Rechtsmittelverfahren am 24. Februar 2014 in ihr Heimatland ausgeschafft. Nach ihrer erneuten Einreise in die Schweiz im Frühling 2016 heiratete sie am 15. Juli 2016 A._ und erhielt vom Migrationsamt eine bis am 14. Juli 2017 gültige Aufenthaltsbewilligung.
B.
Mit Verfügung vom 7. April 2017 widerrief das Migrationsamt die Niederlassungsbewilligung von A._ und die Aufenthaltsbewilligung von B._ und wies beide per 6. Juli 2017 aus der Schweiz weg. Ein dagegen erhobener Rekurs wurde von der Sicherheitsdirektion des Kantons Zürich mit Entscheid vom 26. Oktober 2017 abgewiesen. Die von A._ und B._ in der Folge eingereichte Beschwerde erwies sich gemäss Urteil des Verwaltungsgerichts des Kantons Zürich vom 15. Februar 2018 als erfolglos, wobei beiden für den Fall des Weiterzugs an das Bundesgericht eine Ausreisefrist von einem Monat ab dem Datum eines den Wegweisungspunkt nicht ändernden, bundesgerichtlichen Endentscheides gesetzt wurde.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 27. November 2017 an das Bundesgericht beantragen A._ (Beschwerdeführer) und B._ (Beschwerdeführerin) in einer gemeinsamen Rechtsschrift die Aufhebung des vorinstanzlichen Urteils. Dem Beschwerdeführer sei die Niederlassungsbewilligung zu belassen und der Beschwerdeführerin sei die Aufenthaltsbewilligung zu verlängern respektive zu erteilen. Ausserdem sei der Beschwerde die aufschiebende Wirkung zu gewähren.
Mit Verfügung vom 23. März 2018 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen einen kantonal letztinstanzlichen Endentscheid betreffend Widerruf der Niederlassungsbewilligung ist zulässig, da auf den Fortbestand dieser Bewilligung ein Rechtsanspruch besteht (<ref-ruling> E. 1.2.1 S. 4; Art. 82 lit. a, Art. 83 lit. c Ziff. 2 e contrario, Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG). In Bezug auf den Beschwerdeführer sind die Sachurteilsvoraussetzungen damit erfüllt. Dies gilt auch für die Beschwerdeführerin, welche in vertretbarer Weise einen Anspruch auf Verlängerung ihrer Aufenthaltsbewilligung geltend macht. Ob der Anspruch besteht, ist Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1 S. 179 f.; Urteil 2C_1072/2014 vom 9. Juli 2015 E. 1.2). Auf die Beschwerde ist deshalb einzutreten.
1.2. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), prüft jedoch unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG) nur die geltend gemachten Rechtsverletzungen, sofern rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.5 S. 144). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 2.5 S. 314). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Eine Berichtigung oder Ergänzung der vorinstanzlichen Sachverhaltsfeststellungen ist von Amtes wegen (<ref-law>) oder auf Rüge hin (<ref-law>) möglich. Von den tatsächlichen Grundlagen des vorinstanzlichen Urteils weicht das Bundesgericht jedoch nur ab, wenn diese offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>; <ref-ruling> E. 1.6 S. 144 f.).
1.3. Zur Sachverhaltsfeststellung gehört auch die auf Indizien gestützte Beweiswürdigung. Die Sachverhaltsfeststellung bzw. Beweiswürdigung erweist sich als willkürlich gemäss <ref-law>, wenn sie offensichtlich unhaltbar oder aktenwidrig ist, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (<ref-ruling> E. 2.3 S. 265 f.; Urteile 2C_1072/2014 vom 9. Juli 2015 E. 1.4; 2C_310/2014 vom 25. November 2014 E. 1.2). Eine entsprechende Rüge ist substanziiert vorzubringen; auf rein appellatorische Kritik an der Sachverhaltsfeststellung bzw. Beweiswürdigung geht das Gericht nicht ein (<ref-ruling> E. 2.3 S. 266; <ref-ruling> E. 10.1 S. 444 f.).
2.
2.1. Der Beschwerdeführer rügt eine Verletzung des Anspruchs auf rechtliches Gehör (<ref-law>). Mit vielen Rügen in der (kantonalen) Verwaltungsgerichtsbeschwerde habe sich die Vorinstanz nicht ansatzweise auseinandergesetzt. Diese Verweigerung, die Vorbringen des Beschwerdeführers zu hören, verletze das rechtliche Gehör und das vorinstanzliche Urteil sei in diesem Sinne auch nicht rechtsgenüglich begründet.
2.2. Die aus dem Anspruch auf rechtliches Gehör (<ref-law>) fliessende Begründungspflicht verlangt nicht, dass sich das Gericht mit sämtlichen vorgebrachten Sachverhaltselementen, Beweismitteln und Rügen auseinandersetzt. Vielmehr kann es sich auf die wesentlichen Überlegungen, welche zum Entscheid geführt haben, beschränken, selbst wenn diese fehlerhaft sind. Die Begründung soll dem Betroffenen ermöglichen, die Tragweite des Entscheides zu erfassen und diesen in Kenntnis der Überlegungen des Gerichts anzufechten (<ref-ruling> E. 5.2 S. 70 f.; <ref-ruling> E. 3.2.4 S. 31; <ref-ruling> E. 5.1 S. 238 mit Hinweisen; <ref-ruling> E. 3.3 S. 445). Die Begründungspflicht ist nur dann verletzt, wenn das Gericht auf die für den Ausgang des Verfahrens wesentlichen Vorbringen selbst implizit nicht eingeht (<ref-ruling> E. 5.2 S. 248 f.).
2.3. Der Beschwerdeführer listet eine Reihe von Umständen auf, ohne allerdings aufzuzeigen, inwiefern diese für den Ausgang des Verfahrens wesentlich sei sollen. Auch sonst wird nicht im Einzelnen dargelegt, weshalb der Anspruch auf rechtliches Gehör verletzt sein soll. Die entsprechende Rüge genügt den Anforderungen der qualifizierten Rügepflicht nicht, weshalb darauf nicht einzutreten ist.
3.
3.1. Im Weiteren macht der Beschwerdeführer geltend, der Widerruf der Niederlassungsbewilligung aufgrund von Art. 63 Abs. 1 lit. a i. V. m. <ref-law> sei nicht verhältnismässig und rügt damit sinngemäss eine Verletzung der genannten Bestimmungen. Die Niederlassungsbewilligung einer Person, die sich schon lange in der Schweiz befinde, könne nur mit Zurückhaltung widerrufen werden. Er führt diesbezüglich unter dem Titel von Art. 8 EMRK im Wesentlichen aus, sein strafrechtliches Verschulden sei, da er weder Gewalt- noch Drogendelikte begangen habe, nicht schwer, sondern es handle sich um eine dauerhafte deliktische Tätigkeit geringen Ausmasses. Er sei zudem wegen guter Führung bedingt aus dem Strafvollzug entlassen worden, weshalb von einer guten Legalprognose ausgegangen werden müsse. Zudem habe er eine selbständige Erwerbstätigkeit aufgenommen und seine berufliche Integration sei gut, auch wenn die Vorinstanz dazu nichts vorbringe. Zu seiner Heimat Mazedonien habe er keinen Bezug mehr und könne dort auch keine Arbeit mehr finden. Seine gesamte Familie (Mutter, Bruder, etc.) befinde sich in der Schweiz und sei eingebürgert. Aufgrund seiner Anwesenheit von 36 Jahren in der Schweiz sei sein Lebensmittelpunkt in der Schweiz bzw. er sei in der Schweiz gut integriert. Eine Rückkehr nach Mazedonien wäre für ihn ein "Todesurteil".
3.2. Die Niederlassungsbewilligung kann unter anderem widerrufen werden, wenn die ausländische Person zu einer längerfristigen Freiheitsstrafe, d.h. zu einer solchen von mehr als einem Jahr, verurteilt wurde; dabei spielt es keine Rolle, ob die Sanktion bedingt, teilbedingt oder unbedingt ausgesprochen wurde. In jedem Fall ist die Verhältnismässigkeit der aufenthaltsbeendenden Massnahme zu prüfen (Art. 63 Abs. 1 lit. a i.V.m. <ref-law>; Art. 96 Abs. 1 AuG [in der bis am 31. Dezember 2018 geltenden Fassung]; <ref-ruling> E. 2.1 und 2.3.1 S. 32 ff.; <ref-ruling> E. 4.2 S. 379 ff.; Urteile 2C_532/2017 vom 26. März 2018 E. 2.1 und 2.2; 2C_884/2016 vom 25. August 2017 E. 2.2).
3.3. Vorliegend ist unbestritten, dass der Beschwerdeführer zu einer längerfristigen Freiheitsstrafe im Sinne der Rechtsprechung, nämlich zu einem Freiheitsentzug von 45 Monaten verurteilt wurde. Die Vorinstanz hat erwogen, dass der entsprechenden Verurteilung (vom 29. November 2016) eine vierjährige deliktische Tätigkeit, teilweise gewerbsmässig, zugrunde lag. Zudem habe der Beschwerdeführer nach einer ersten Phase der Untersuchungshaft wegen anderen Delikten im Jahr 2012 sofort nach der Entlassung wieder angefangen zu delinquieren. Seine Straffälligkeit sei jeweils nur durch Untersuchungshaft unterbrochen worden. Die Wiederholungsgefahr sei hoch. Trotz Anwesenheit von über 36 Jahren habe er sich in der Schweiz nicht erfolgreich integriert. Seinen finanziellen Verpflichtungen sei er während Jahren nicht nachgekommen. Er spreche mazedonisch. Ausserdem könne ihm sein Vater, der noch gute Kontakte zu Mazedonien habe, bei der Wiedereingliederung in sein Heimatland helfen. In diesem Zusammenhang ist unbestritten, dass der Beschwerdeführer im Jahr 2004 in Mazedonien eine andere Frau (als die Beschwerdeführerin) geheiratet hat. Ebenfalls unbestritten ist, dass sein Vater mit ihm nach Antritt des Strafvollzugs wieder Kontakt aufgenommen hat. Das öffentliche Interesse an der Wegweisung überwiegt deshalb nach Ansicht der Vorinstanz das private Interesse am Verbleib des Beschwerdeführers in der Schweiz.
3.4. Was die berufliche Integration des Beschwerdeführers in der Schweiz anbelangt, finden sich dazu im vorinstanzlichen Urteil keine positiven Feststellungen, wobei sich die Ausführungen in der Beschwerde an die Vorinstanz darin erschöpfen, der Beschwerdeführer habe eine selbständige Erwerbstätigkeit aufgenommen. Entgegen dem Beschwerdeführer ist es nicht Sache der Vorinstanz, dazu etwas vorzubringen, sondern der Untersuchungsgrundsatz wird durch die Mitwirkungspflicht der ausländischen Person (<ref-law>) relativiert. Diese (Mitwirkungspflicht) kommt insbesondere bei Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand erhoben werden können (<ref-ruling> E. 8.6.4 S. 496 f. mit Hinweisen; Urteile 2C_118/2017 vom 18. August 2017 E. 4.2; 2C_171/2016 vom 25. August 2016 E. 3.2.2). Es wäre deshalb Sache des Beschwerdeführers gewesen, seine erfolgreiche berufliche Integration im vorinstanzlichen Verfahren darzulegen.
3.5. Die vorinstanzliche Interessenabwägung ist aufgrund der bisher genannten Umstände nicht zu beanstanden. Der Beschwerdeführer hat ab dem Alter von 22 Jahren mit wenigen Unterbrüchen während rund 23 Jahren regelmässig delinquiert, wobei mit einer einzelnen Verurteilung zu 45 Monaten Freiheitsstrafe das Kriterium der längerfristigen Freiheitsstrafe deutlich erfüllt ist. Eine positive, gegenläufige Entwicklung ist gemäss vorinstanzlich und verbindlich festgestelltem Sachverhalt nicht ersichtlich, abgesehen davon, dass der Beschwerdeführer einen Schuldenberg von fast Fr. 300'000.-- angehäuft hat. Die vorinstanzliche Anwendung von Art. 63 Abs. 1 lit. a i.V.m. <ref-law>, insbesondere die Verhältnismässigkeitsprüfung, und demzufolge der Widerruf der Niederlassungsbewilligung des Beschwerdeführers, erweisen sich damit als bundesrechtskonform.
4.
4.1. Da der Beschwerdeführer nach dem Gesagten kein Aufenthaltsrecht in der Schweiz hat, kann die Beschwerdeführerin für sich kein solches aus Art. 43 AuG (in der bis am 31. Dezember 2018 geltenden Fassung; ab 1. Januar 2019 in revidierter Fassung <ref-law>) ableiten. Sie beruft sich jedoch auf ein Aufenthaltsrecht gestützt auf Art. 8 EMRK (Recht auf Achtung des Familienlebens) abgeleitet aus einem Pflegeverhältnis mit ihrer in der Schweiz wohnhaften Nichte, welche über das Schweizer Bürgerrecht verfügt. Gemäss vorinstanzlicher Sachverhaltsfeststellung datiert der Pflegevertrag zwischen der pflegebedürftigen Nichte und der als Pflegemutter agierenden Beschwerdeführerin vom 21. November 2017, wobei das Pflegeverhältnis nach diesem Vertrag erst am 22. August 2017 begonnen hat.
4.2. Die Beschwerdeführerin rügt diesbezüglich zunächst eine ungenügende und willkürliche Sachverhaltsfeststellung. Es sei Sache der Behörden gewesen, aufgrund der Untersuchungsmaxime das Vorliegen eines Abhängigkeitsverhältnisses im Rahmen des Pflegeverhältnisses abzuklären. Diesbezüglich legt die Beschwerdeführerin erstmals vor Bundesgericht ein Schreiben des kjz (Kinder- und Jugendhilfezentrum) U._ vom 1. März 2018 an den Rechtsvertreter der Beschwerdeführer vor. Gemäss Beschwerdeführerin belegt dieses Schreiben ein Abhängigkeitsverhältnis der Nichte gegenüber der Beschwerdeführerin, wobei es sich um ein zulässiges, unechtes Novum im Sinne von <ref-law> handle.
4.3. Art. 8 EMRK verschafft keinen Anspruch auf Aufenthalt in einem bestimmten Staat. Dennoch kann es das in Art. 8 EMRK geschützte Recht auf Achtung des Familienlebens verletzen, wenn einer ausländischen Person, deren Familienangehörige sich hier aufhalten und über ein gefestigtes Aufenthaltsrecht verfügen, die Anwesenheit untersagt und damit ihr Zusammenleben vereitelt wird (<ref-ruling> E. 4.2 S. 96; <ref-ruling> E. 5.1 S. 26; <ref-ruling> E. 6.1 S. 46 mit Hinweisen; <ref-ruling> E. 1.3.1 S. 145 f.; Urteil 2C_1009/2018 vom 30. Januar 2019 E. 3.1). Art. 8 EMRK bzw. <ref-law> schützt in diesem Zusammenhang in erster Linie die Kernfamilie, d.h. die Gemeinschaft der Ehegatten mit ihren minderjährigen Kindern (BGE <ref-ruling> E. 1.3.2 S. 146; Urteil 2C_301/2016 vom 19. Juli 2017 E. 5). Über die Kernfamilie hinaus kann Art. 8 EMRK auch für nahe Verwandte einer in der Schweiz fest anwesenheitsberechtigten Person ein Aufenthaltsrecht entstehen lassen. Grundsätzlich setzt dies allerdings unter anderem voraus, dass die verwandte, ausländische Person von der in der Schweiz fest anwesenheitsberechtigten Person abhängig bzw. pflegebedürftig ist und nicht umgekehrt (Urteile 2C_301/2016 vom 19. Juli 2017 E. 5.3; 2C_430/2012 vom 21. Mai 2012 E. 3.2.1; 2C_451/2007 vom 22. Januar 2008 E. 2.2). Im Verhältnis der Eltern zu ihren volljährigen Kindern ist dieses Erfordernis zu relativieren in dem Sinne, dass die Abhängigkeit bzw. Pflegebedürftigkeit auch auf Seiten der in der Schweiz anwesenheitsberechtigten Person bestehen kann (Urteile 2C_253/2010 vom 18. Juli 2011 E. 2 [pflegebedürftige, anwesenheitsberechtigte, Mutter]; 2C_942/2010 vom 27. April 2011 [pflegebedürftige, anwesenheitsberechtigte, volljährige Tochter]). Eine solche Konstellation besteht jedoch vorliegend nicht. Dass kein Abhängigkeitsverhältnis der bald 43-jährigen Beschwerdeführerin gegenüber ihrer 13-jährigen Nichte besteht, ist unbestritten. Auch sonst sind keine Umstände ersichtlich, welche darüber hinaus im Einzelfall ein Anwesenheitsrecht gestützt auf Art. 8 EMRK verschaffen würden (vgl. vielmehr Urteil 2C_293/2018 vom 5. Oktober 2018). Aus dem genannten Pflegeverhältnis lässt sich deshalb kein Aufenthaltsrecht gestützt auf Art. 8 EMRK zugunsten der Beschwerdeführerin ableiten. Es kann demnach offenbleiben, ob das erwähnte Schreiben des kjz U._ als Novum zu berücksichtigen und ein Abhängigkeitsverhältnis der Nichte gegenüber der Beschwerdeführerin belegen würde. Ebenso erübrigt es sich, auf die in diesem Zusammenhang erhobene, abgesehen davon unsubstanziierte Sachverhaltsrüge einzutreten. In Bezug auf die Kindesinteressen ist festzuhalten, dass die Nichte aufgrund ihres Schweizer Bürgerrechts in der Schweiz verbleiben und fortan durch Dritte betreut werden kann, sodass den Kindesinteressen genüge getan ist. Soweit die Beschwerdeführerin sinngemäss rügt, Art. 8 EMRK sei in Bezug auf ihr Recht auf Achtung des Privatlebens verletzt, erweist sich das vorinstanzliche Urteil damit als rechtskonform.
4.4. Der Beschwerdeführer rügt gestützt auf seine Ehe mit der Beschwerdeführerin eine Verletzung seines Rechts auf Achtung des Familienlebens gemäss Art. 8 EMRK. Da die Beschwerdeführerin einen Anspruch auf Aufenthalt in der Schweiz habe, könne er ebenfalls ein Aufenthaltsrecht geltend machen. Wie dargelegt verfügt die Beschwerdeführerin jedoch über kein Aufenthaltsrecht in der Schweiz, weshalb der Beschwerdeführer seinerseits im Rahmen von Art. 8 EMRK kein solches daraus ableiten kann. Auch in Bezug auf den Beschwerdeführer ist das Recht auf Achtung des Familienlebens im Sinne von Art. 8 EMRK bzw. <ref-law> somit nicht verletzt.
5.
Im Weiteren führt der Beschwerdeführer aus, es sei unbestritten, dass er sich bezüglich Aufenthalt auf das Recht Achtung des Privatlebens gemäss Art. 8 EMRK berufen könne. Inwiefern dieses Recht vorliegend verletzt sein soll, wird jedoch nicht dargelegt. Mangels substanziierter Rüge ist deshalb nicht darauf einzutreten. Im Übrigen würde der Beschwerdeführer die Voraussetzungen für ein Aufenthaltsrecht gestützt auf das Recht auf Achtung des Privatlebens nicht erfüllen, denn ein solches setzt unter anderem voraus, dass die ausländische Person in der Schweiz beruflich gut integriert ist und nie straffällig geworden ist, was beim Beschwerdeführer nicht der Fall wäre (<ref-ruling> E. 4 S. 279 f.).
6.
Die Beschwerde erweist sich damit als unbegründet und ist abzuweisen. Die Beschwerdeführer tragen die Gerichtskosten des bundesgerichtlichen Verfahrens unter solidarischer Haftung (Art. 65 und Art. 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 23. April 2019
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Quinto